package com.wufeng.sort;

/**
 * 插入排序 InsertionSort
 * 默认前面的数组元素时已排序的，当前元素与前面的元素以此比较，小于交互位置，直到大于前面的数
 *
 */
public class InsertionSort {
    public static int[] sort(int[] array){
        if (array.length == 0)
            return array;
        int value;
        for (int i = 1; i < array.length; i++) {
            int index = i;
            value = array[index];
            while(index != 0 && value < array[index-1]){
                array[index] = array[index -1];
                index --;
            }
            array[index] = value;
        }
        return array;
    }

}
